package 链表;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author zxl
 * @Date 2021/12/19 13:40
 * @Desc
 */
public class 相交链表 {


    public static List<Node> initData() {

        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;

        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 6;
        Node node7 = new Node();
        node7.value = 7;
        Node node8 = new Node();
        node8.value = 8;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node6.next = node7;
        node7.next = node8;
        node8.next = node3;
        List<Node> list = new ArrayList<>();
        list.add(node1);
        list.add(node6);
        return list;
    }

    /**
     * 找到两个单链表相交的起始节点
     * 如果两个链表没有交点，返回 null。
     * 在返回结果后，两个链表仍须保持原有的结构。
     * 可假定整个链表结构中没有循环。
     * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     *
     * @param args
     */
    public static void main(String[] args) {
        List<Node> list = initData();
        Node head1 = list.get(0);
        Node head2 = list.get(1);
        System.out.println("链表数据1：" + head1.toString());
        System.out.println("链表数据2：" + head2.toString());
//        Node connectionNode = findConnectionNodeByStack(head1,head2);
        Node connectionNode = findConnectionNodeByLength(head1, head2);
        if (connectionNode == null) {
            System.out.println("不存在相交节点");
        } else {
            System.out.println("相交节点：" + connectionNode.value);
        }
    }


    public static Node intersect(Node head1, Node head2) {

        Node temp1 = head1, temp2 = head2;

        while (temp1 != null && temp2 != null) {
            if (temp1.value == temp2.value) {
                return temp1;
            }
            temp1 = temp1.next;
            temp2 = temp2.next;
            if (temp1 == null && temp2 != null) {
                temp1 = head2;
            }
            if (temp2 == null && temp1 != null) {
                temp2 = head1;
            }
        }
        return null;

    }


    /**
     * 通过长度计算：假设A、B两条链表重合部分长度是c，A链表仅属于自己的长度是a，B链表仅属于自己的长度是b，
     * 那么a+c+b=b+c+a
     *
     * @param headA
     * @param headB
     * @return
     */
    public static Node findConnectionNodeByLength(Node headA, Node headB) {
        Node a = headA;
        Node b = headB;
        while (a != null && b != null) {
            if (a.value == b.value) {
                return a;
            }
            a = a.next;
            b = b.next;
            if (a == null && b != null) {
                a = headB;
            }
            if (a != null && b == null) {
                b = headA;
            }

        }
        return null;

    }

    /**
     * 使用栈
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node findConnectionNodeByStack(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Stack<Node> nodeStack1 = new Stack<>();
        Stack<Node> nodeStack2 = new Stack<>();
        while (head1 != null) {
            nodeStack1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            nodeStack2.push(head2);
            head2 = head2.next;
        }
        while (!nodeStack1.isEmpty() && !nodeStack2.isEmpty()) {
            Node pop1 = nodeStack1.pop();
            Node pop2 = nodeStack2.pop();
            if (pop1.value != pop2.value) {
                return pop1.next;
            }
        }
        return null;
    }

}
